//组合总和二 力扣40
//回溯算法 树层去重(本题需要) 树枝去重（本题不需要）
class Solution {
public:
	vector<vector<int>> ans;
	vector<int> path;
	int sum = 0;
	vector<bool> st = vector<bool>(105);
	void backtracking(vector<int> candidates,int target,int startindex)
	{
		if(sum == target)
		{
			ans.push_back(path);
			return;
		}
		for(int i = startindex; i < candidates.size() && sum + candidates[i] <= target; i++)
		{   
			//或写成
			//if(i > 0 && candidates[i]== candidates[i-1] && i > startindex)
			if(i > 0 && candidates[i]== candidates[i-1] && st[i-1] == false)
				continue;
			path.push_back(candidates[i]);
			st[i] = true;
			sum += candidates[i];
			backtracking(candidates,target,i+1);
			path.pop_back();
			sum -= candidates[i];
			st[i] = false;
		}
	}
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		sort(candidates.begin(),candidates.end());
		backtracking(candidates,target,0);
		return ans;
	}
};
